package week02

// 51. N 皇后
// https://leetcode-cn.com/problems/n-queens/

func solveNQueens(n int) [][]string {
	var used = make(map[int]bool)
	var plus = make(map[int]bool)
	var minus = make(map[int]bool)
	list := solveNQueens2(n, used, plus, minus, []int{}, [][]int{}, 0)

	var result [][]string
	for _, l := range list {
		var res []string
		for _, col := range l {
			byt := makeByteSlice(n)
			byt[col] = 'Q'
			res = append(res, string(byt))
		}
		result = append(result, res)
	}

	return result
}

func solveNQueens2(n int, used, plus, minus map[int]bool, temp []int, ans [][]int, row int) [][]int {
	if row == n {
		var res = make([]int, len(temp))
		copy(res, temp)
		return append(ans, res)
	}
	for col := 0; col < n; col++ {
		if used[col] || plus[row+col] || minus[row-col] {
			continue
		}
		used[col] = true
		plus[row+col] = true
		minus[row-col] = true
		temp = append(temp, col)
		ans = solveNQueens2(n, used, plus, minus, temp, ans, row+1)
		temp = temp[:len(temp)-1]
		minus[row-col] = false
		plus[row+col] = false
		used[col] = false
	}
	return ans
}

func makeByteSlice(n int) []byte {
	var byt = make([]byte, n)
	for i := range byt {
		byt[i] = '.'
	}
	return byt
}
